===========i=1∑nj=1∑mμ(lcm(i,j))d=1∑min(n,m)i=1∑nj=1∑m[gcd(i,j)=d]μ(dij)d=1∑min(n,m)i=1∑⌊dn⌋j=1∑⌊dm⌋[gcd(i,j)=1]μ(ijd)d=1∑min(n,m)t=1∑min(⌊dn⌋,⌊dm⌋)μ(t)i=1∑⌊dtn⌋j=1∑⌊dtm⌋μ(ijdt2)T=1∑min(n,m)d∣T∑μ(d)i=1∑⌊Tn⌋j=1∑⌊Tm⌋μ(dTij)T=1∑min(n,m)i=1∑⌊Tn⌋j=1∑⌊Tm⌋μ(Tij)T=1∑min(n,m)μ(T)i=1∑⌊Tn⌋j=1∑⌊Tm⌋[gcd(i,T)=1][gcd(j,T)=1][gcd(i,j)=1]μ(i)μ(j)T=1∑min(n,m)μ(T)d=1∑min(⌊Tn⌋,⌊Tm⌋)μ(d)[gcd(d,T)=1]i=1∑⌊Tdn⌋j=1∑⌊Tdm⌋[gcd(i,T)=1][gcd(i,d)=1]μ(i)μ(d)[gcd(j,T)=1][gcd(j,d)=1]μ(j)μ(d)T=1∑min(n,m)d=1∑min(⌊Tn⌋,⌊Tm⌋)μ(Td)μ2(d)i=1∑⌊Tdn⌋j=1∑⌊Tdm⌋[gcd(i,dT)=1]μ(i)[gcd(j,dT)=1]μ(j)T=1∑min(n,m)μ(T)d∣T∑μ2(d)i=1∑⌊Tn⌋j=1∑⌊Tm⌋[gcd(i,T)=1]μ(i)[gcd(j,T)=1]μ(j)T=1∑min(n,m)μ(T)⎝⎛d∣T∑μ2(d)⎠⎞⎝⎛i=1∑⌊Tn⌋[gcd(i,T)=1]μ(i)⎠⎞⎝⎛j=1∑⌊Tm⌋[gcd(j,T)=1]μ(j)⎠⎞T=1∑min(n,m)μ(T)⎝⎛d∣T∑μ2(d)⎠⎞⎝⎛i=1∑⌊Tn⌋μ(iT)⎠⎞⎝⎛j=1∑⌊Tm⌋μ(jT)⎠⎞
线筛出 ∑d∣Tμ2(d) 后直接暴力计算,复杂度 O(Tnlnn)
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 1e6 , Mod = 998244353;
int prnum , prime[ MAXN + 5 ] , mu[ MAXN + 5 ] , mu2[ MAXN + 5 ];
int lowk[ MAXN + 5 ] , loww[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
mu[ 1 ] = 1; mu2[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) {
prime[ ++ prnum ] = i;
lowk[ i ] = i; loww[ i ] = 1;
mu[ i ] = -1 , mu2[ i ] = 2;
}
for( int j = 1 ; j <= prnum && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) {
lowk[ i * prime[ j ] ] = lowk[ i ] * prime[ j ] , loww[ i * prime[ j ] ] = loww[ i ] + 1;
mu2[ i * prime[ j ] ] = 1ll * mu2[ i / lowk[ i ] ] * ( loww[ i ] + 2 ) % Mod;
break;
}
lowk[ i * prime[ j ] ] = prime[ j ] , loww[ i * prime[ j ] ] = 1;
mu[ i * prime[ j ] ] = -mu[ i ];
mu2[ i * prime[ j ] ] = mu2[ i ] * mu2[ prime[ j ] ];
}
}
}
int Calc( int n , int T ) {
int Ans = 0;
for( int i = 1 ; i <= n / T ; i ++ ) Ans += mu[ i * T ];
return Ans;
}
int Solve( int n , int m ) {
int Ans = 0;
for( int i = 1 ; i <= min( n , m ) ; i ++ )
if( mu[ i ] ) Ans = ( Ans + 1ll * mu[ i ] * mu2[ i ] * Calc( n , i ) * Calc( m , i ) % Mod ) % Mod;
return ( Ans + Mod ) % Mod;
}
int T , n , m;
int main( ) {
sieve();
scanf("%d",&T);
while( T -- ) {
scanf("%d %d",&n,&m);
printf("%d\n", Solve( n , m ) );
}
return 0;
}